package tree;

import java.util.*;
import java.util.function.DoublePredicate;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int x) {
        val = x;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    public int maxDepth(TreeNode node){
        if(node == null){
            return 0;
        }
        return Math.max(maxDepth(node.left),maxDepth(node.right)) + 1;
    }

    //层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                currentLevel.add(currentNode.val);

                if (currentNode.left != null) {
                    queue.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.add(currentNode.right);
                }
            }

            result.add(currentLevel);
        }

        return result;
    }

    //给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
    //
    //百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Set<TreeNode> pNodes = new LinkedHashSet<>();
        Set<TreeNode> qNodes = new LinkedHashSet<>();
        TreeNode node = root;
        dfs(pNodes,node,p);
        dfs(qNodes,node,q);
        for (TreeNode qNode : qNodes) {
            if(pNodes.contains(qNode)){
                return qNode;
            }
        }
        return null;
    }

    private TreeNode node;

    //递归法
    public TreeNode lowestCommonAncestorByReturn(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root,p.val,q.val);
        return node;
    }

    public boolean dfs(TreeNode root, int p, int q){
        if(root == null) return false;

        Boolean pB = dfs(root.left,p,q) ;
        Boolean qB = dfs(root.right,p,q);

        boolean b = (root.val == p || root.val ==q);
        if((b && (pB || qB)) || (pB && qB)){
            node = root;
            return true;
        }
        return b || pB || qB;
    }


    public boolean dfs(Set set,TreeNode root, TreeNode target){
        if(root == null){
            return false;
        }
        if(root == target){
            set.add(root);
            return true;
        }
        boolean dfs = dfs(set, root.left, target);
        boolean dfsR = dfs(set, root.right, target);
        if(dfs || dfsR){
            set.add(root);
        }
        return dfs || dfsR;
    }

    //有序二叉树的下一个元素
    public TreeNode queryNextNode(TreeNode root, TreeNode node){
        return null;
    }


    //路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
    //
    //路径和 是路径中各节点值的总和。
    //
    //给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。
    private int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        int targetMax = 0;
        helpMax(root);
       // targetMax = Math.max(targetMax,max);
        return max;
    }

    public int helpMax(TreeNode root){
        if(root == null){
            return 0;
        }
        int right = 0;
        if(root.right != null){
            right = helpMax(root.right);
        }
        int left = 0;
        if(root.left != null){
            left = helpMax(root.left);
        }
        if(root.val < 0 && root.left != null && root.right != null){
            int maxNode = Math.max(left, right);
            max = Math.max(maxNode,max);
        }
        max = Math.max(root.val + (Math.max(left, 0)) + (Math.max(right, 0)),max);
        return root.val + (Math.max(Math.max(left, 0),Math.max(right, 0)));
    }
        public static void main(String[] args) {
//            TreeNode treeNode = new TreeNode(0); // 用于调用方法的实例
//
//            // 构建树结构: [5,4,8,11,null,13,4,7,2,null,null,null,1]
//            //       5
//            //      / \
//            //     4   8
//            //    /   / \
//            //   11  13  4
//            //  / \      \
//            // 7   2      1
//
//            TreeNode root = new TreeNode(5);
//            TreeNode node4 = new TreeNode(4);
//            TreeNode node8 = new TreeNode(8);
//            TreeNode node11 = new TreeNode(11);
//            TreeNode node13 = new TreeNode(13);
//            TreeNode node4_2 = new TreeNode(4);
//            TreeNode node7 = new TreeNode(7);
//            TreeNode node2 = new TreeNode(2);
//            TreeNode node1 = new TreeNode(1);
//
//            // 构建树的连接关系
//            root.setLeft(node4);
//            root.setRight(node8);
//
//            node4.setLeft(node11);
//            // node4.right 为 null
//
//            node8.setLeft(node13);
//            node8.setRight(node4_2);
//
//            node11.setLeft(node7);
//            node11.setRight(node2);
//
//            // node13.left 和 node13.right 都为 null
//
//            // node4_2.left 为 null
//            node4_2.setRight(node1);
//
//            // 测试最大路径和
//            System.out.println("树 [5,4,8,11,null,13,4,7,2,null,null,null,1] 的最大路径和: " + treeNode.maxPathSum(root));
//
//            // 预期路径分析:
//            // 最大路径应该是: 7 -> 11 -> 4 -> 5 -> 8 -> 13
//            // 路径和为: 7 + 11 + 4 + 5 + 8 + 13 = 48


            TreeNode treeNode = new TreeNode(0); // 用于调用方法的实例

            // 测试用例1: 普通二叉树
            //       1
            //      / \
            //     2   3
            TreeNode root1 = new TreeNode(1);
            root1.setLeft(new TreeNode(2));
            root1.setRight(new TreeNode(3));
            System.out.println("测试用例1结果: " + treeNode.maxPathSum(root1));
            // 预期结果: 6 (路径: 2 -> 1 -> 3)

            // 测试用例2: 包含负数的二叉树
            //      -10
            //      /  \
            //     9   20
            //        /  \
            //       15   7
            TreeNode root2 = new TreeNode(-10);
            root2.setLeft(new TreeNode(9));
            TreeNode right2 = new TreeNode(20);
            right2.setLeft(new TreeNode(15));
            right2.setRight(new TreeNode(7));
            root2.setRight(right2);
            System.out.println("测试用例2结果: " + treeNode.maxPathSum(root2));
            // 预期结果: 42 (路径: 15 -> 20 -> 7)

            // 测试用例3: 全为负数的二叉树
            //      -3
            //      / \
            //    -9  -2
            TreeNode root3 = new TreeNode(-3);
            root3.setLeft(new TreeNode(-9));
            root3.setRight(new TreeNode(-2));
            System.out.println("测试用例3结果: " + treeNode.maxPathSum(root3));
            // 预期结果: -2 (选择最大的单个节点)

            // 测试用例4: 单节点树
            TreeNode root4 = new TreeNode(5);
            System.out.println("测试用例4结果: " + treeNode.maxPathSum(root4));
            // 预期结果: 5
        }


//    public static void main(String[] args) {
//        // 创建测试二叉树:
//        //       3
//        //      / \
//        //     5   1
//        //    / \ / \
//        //   6  2 0  8
//        //     / \
//        //    7   4
//
//        TreeNode root = new TreeNode(3);
//        TreeNode node5 = new TreeNode(5);
//        TreeNode node1 = new TreeNode(1);
//        TreeNode node6 = new TreeNode(6);
//        TreeNode node2 = new TreeNode(2);
//        TreeNode node0 = new TreeNode(0);
//        TreeNode node8 = new TreeNode(8);
//        TreeNode node7 = new TreeNode(7);
//        TreeNode node4 = new TreeNode(4);
//
//        root.setLeft(node5);
//        root.setRight(node1);
//        node5.setLeft(node6);
//        node5.setRight(node2);
//        node1.setLeft(node0);
//        node1.setRight(node8);
//        node2.setLeft(node7);
//        node2.setRight(node4);
//
//        TreeNode treeNode = new TreeNode(0); // 用于调用方法的实例
//
//        // 测试用例1: 节点5和节点1的最近公共祖先应该是根节点3
//        TreeNode result1 = treeNode.lowestCommonAncestorByReturn(root, node5, node1);
//        System.out.println("节点5和节点1的最近公共祖先: " + (result1 != null ? result1.getVal() : "null"));
//
//        // 测试用例2: 节点5和节点4的最近公共祖
//        // 先应该是节点5
//        TreeNode result2 = treeNode.lowestCommonAncestorByReturn(root, node5, node4);
//        System.out.println("节点5和节点4的最近公共祖先: " + (result2 != null ? result2.getVal() : "null"));
//
//        // 测试用例3: 节点6和节点2的最近公共祖先应该是节点5
//        TreeNode result3 = treeNode.lowestCommonAncestorByReturn(root, node6, node2);
//        System.out.println("节点6和节点2的最近公共祖先: " + (result3 != null ? result3.getVal() : "null"));
//
//        // 测试用例4: 相同节点的情况
//        TreeNode result4 = treeNode.lowestCommonAncestorByReturn(root, node5, node5);
//        System.out.println("节点5和节点5的最近公共祖先: " + (result4 != null ? result4.getVal() : "null"));
//    }


}
